/*
Source : https://leetcode.com/problems/contains-duplicate/
Author : nflush@outlook.com
Date   : 2016-07-05
*/
/*
217. Contains Duplicate

    Total Accepted: 99778
    Total Submissions: 237050
    Difficulty: Easy

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Subscribe to see which companies asked this question
*/

// 52ms
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int, bool> m;
        for (auto item : nums) {
            if (m.find(item) != m.end()) return true;
            m[item]=true;
        }
        return false;
    }
};

// 51ms
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int, bool> m(nums.size());
        for (auto item : nums) {
            if (m.find(item) != m.end()) return true;
            m[item]=true;
        }
        return false;
    }
};

// 48ms
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        if (nums.size() < 2) return false;
        if (2 == nums.size()) return nums[0] == nums[1];
        unordered_map<int, bool> m(nums.size());
        for (auto item : nums) {
            if (m.find(item) != m.end()) return true;
            m[item]=true;
        }
        return false;
    }
};

// 24ms
class Solution {
private:
    int *hashMap;
    int size;
    void hashMapInit(int sz){
        hashMap = new int[sz*2];
        memset(hashMap, 0, sizeof(int)*sz*2);
        size = sz*2;
    }
    bool hashInsert(int val){
        if (val == 0){
            if (hashMap[0] != -1){
                hashMap[0] = -1;
                return false;
            }else
                return true;
        }
        int key = val % size;
        if (key < 0) key = (0 - key)% size;
        int x = 0;
        while (hashMap[key] != 0){
            if (hashMap[key] == val){
                return true;
            } else {
                key = ((key + val) ^ (size -x++)) % size;
                if (key < 0) key = (0 - key)% size;
            }
        }
        hashMap[key] = val;
        return false;
    }
public:
    bool containsDuplicate(vector<int>& nums) {
        if (nums.size() < 2) return false;
        if (2 == nums.size()) return nums[0] == nums[1];
        hashMapInit(nums.size());
        for (auto it:nums){
            if (hashInsert(it)) return true;
        }
        delete [] hashMap;
        return false;
    }
};

// 24ms
class Solution {
private:
    int *hashMap;
    int size;
    void hashMapInit(int sz){
        hashMap = static_cast<int *>(malloc(sizeof(int)*sz*2));
        memset(hashMap, 0, sizeof(int)*sz*2);
        size = sz*2;
    }
    bool hashInsert(int val){
        if (val == 0){
            if (hashMap[0] != -1){
                hashMap[0] = -1;
                return false;
            }else
                return true;
        }
        int key = val % size;
        if (key < 0) key = (0 - key)% size;
        int x = 0;
        while (hashMap[key] != 0){
            if (hashMap[key] == val){
                return true;
            } else {
                key = ((key + val) ^ (size -x++)) % size;
                if (key < 0) key = (0 - key)% size;
            }
        }
        hashMap[key] = val;
        return false;
    }
public:
    bool containsDuplicate(vector<int>& nums) {
        if (nums.size() < 2) return false;
        if (2 == nums.size()) return nums[0] == nums[1];
        hashMapInit(nums.size());
        for (auto it:nums){
            if (hashInsert(it)) return true;
        }
        free(hashMap);
        return false;
    }
};

